Everything about Reconstruction Conjecture totally explained
Informally, the
reconstruction conjecture in
graph theory says that graphs are determined uniquely by their subgraphs. It is due to
Kelly and
Ulam.
Formal statement
Given a graph
, a
vertex-deleted subgraph of
is an
induced subgraph formed by deleting exactly one vertex from
.
For a graph
, the
deck of G, denoted
, is the collection of all vertex-deleted subgraphs of
. Note that in general this isn't a set, but a
multiset, since two vertex deleted subgraphs may be isomorphic, but we still want to count their multiplicity. Each graph in
is called a
card.
With these definitions, the conjecture can be stated as:
Reconstruction Conjecture: Any two graphs on at least three vertices with the same decks are isomorphic.
(The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.)
Harary suggested a stronger version of the conjecture:
Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted induced subgraphs are isomorphic.
Verification
The conjecture has been verified for a number of infinite classes of graphs, such as
regular graphs (graphs in which all vertices have the same number of edges attached to them).
Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 11 vertices (
McKay).
In a probabilistic sense, it has been shown (
Bollobás) that almost all graphs are reconstructible. This means that the probability that a randomly chosen graph on
vertices isn't reconstructible goes to 0 as
goes to infinity. In fact, it was shown that not only are almost all graphs reconstructible, but in fact that the entire deck isn't necessary to reconstruct them — almost all graphs have the property that there exist three cards in their deck that uniquely determine the graph.
Other structures
It has been shown that the following are
not in general reconstructible:
Further Information
Get more info on 'Reconstruction Conjecture'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://reconstruction_conjecture.totallyexplained.com">Reconstruction conjecture Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
